// -*- coding: utf-8 -*- 
/**
 * Project: AlgorithmsLearn
 *
 * @author: yanking
 * Create time: 2022-03-24 18:08
 * IDE: IntelliJ IDEA
 * Introduction:
 */
package com.LeetcodeRepeat;

public class FindKthNumber {
    /**
     * 寻找数组串中第k个字典序数字
     */
    public int findKthNumber(int n, int k) {
        int length = String.valueOf(n).length();
        if (k > length) {
            return -1;
        }
        int ans = 1;
        while (k > 1) {
            int cnt = getCnt(ans, n);
            if (cnt < k) {
                k -= cnt;
                ans++;
            } else {
                k--;
                ans *= 10;
            }
        }
        return ans;
    }

    /**
     * 返回当前前缀数子到limit的数字个数之和
     */
    private int getCnt(int prefix, int limit) {
        String y = String.valueOf(limit);
        String x = String.valueOf(prefix);
        int k = y.length() - x.length();
        int ans = 0;
        for (int i = 0; i < k; i++) {
            ans += Math.pow(10, i);
        }
        int u = Integer.parseInt(y.substring(0, x.length()));
        if (u == prefix) {
            ans += limit - prefix * Math.pow(10, k) + 1;
        } else if (u > prefix) {
            ans += Math.pow(10, k);
        }
        return ans;
    }


}
